Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands are certain to increase.
As a business grows, so can its network, increasing in the number of network elements coupled to the network, the number of network links, and also geographic diversity. Over time, a business' network can include physical locations scattered throughout a city, a state, a country, or the world. Since it can be prohibitively expensive to create a private network that spans these great distances, many businesses opt to rely upon a third-party provider's transport network to provide connectivity between the disparate geographic sites of the business' network elements. In order for the business' network to seamlessly function through the provider network, the provider network must be able to provide a medium for transmission of all the business' various types of datastreams, including multicast transmission.
Multicast routing protocols enable multicast transmission (i.e., one-to-many connections and many-to-many connections) by replicating a multicast packet close to the destination of that packet, obviating the need for multiple unicast connections for the same purpose; thus, saving network bandwidth and improving throughput. Upon receiving a multicast packet, a network node can examine a multicast group destination address (GDA) of the packet and determine whether downstream subscribers to the multicast packet (i.e., members of the multicast group) are connected to the network node (either directly or indirectly). The network node can then replicate the multicast packet as needed and transmit the replicated packets to any connected subscribers.
FIG. 1A is a simplified block diagram of a network transporting a multicast transmission. Network router elements 110, 120, 130 and 140 are coupled through network links 150, 160, and 170. Network router element 110 is also coupled to network elements 111 and 112; network router element 120 is coupled to network element 121; network router element 130 is coupled to network elements 131 and 132; and, network router element 140 is coupled to network element 141. Such coupling between the network router elements and the network elements can be direct or indirect (e.g., via a L2 network device or another network router element).
For the purposes of this illustration, network element 111 is a multicast source transmitting to a multicast group that includes receiving network elements 112, 121, 131, 132 and 141. A multicast datastream, having a group destination address to which the above network elements have subscribed as receiver members, is transmitted from network element 111 to network router element 110 (illustrated by the arrow from 111 to 110). Network router element 110 determines where to forward packets in the multicast datastream by referring to a multicast group address table that identifies each port of network router element 110 that is coupled, directly or indirectly, to a subscribing member of the multicast group. Network router element 110 then replicates packets of the multicast datastream and then transmits the packets from the identified ports to network element 112, network router element 120 and network router element 130.
Network router elements 120 and 130 can inform network router element 110 that they are coupled to a subscribing member of a multicast datastream using, for example, a protocol independent multicast (PIM) multicast message. Using PIM, network router elements 120 and 130 can send messages indicating that they need to join (a “JOIN” message) or be excluded from (a “PRUNE” message) receiving packets directed to a particular multicast group or being transmitted by a particular source. Similarly, a network element can inform a first-hop network router element that the network element wishes to be a subscriber to a multicast group by sending a membership report request through a software protocol such as internet group management protocol (IGMP). When a network element wishes to subscribe to a multicast transmission, an IGMP membership request frame can be transmitted by the network element. An IGMP-enabled network router element (or a L2 network device) can have “snooping” software executing to read such a frame and build a corresponding entry in the multicast group address table.
Upon receipt by network router elements 120 and 130, packets from the multicast datastream will be replicated as needed by those network router elements to provide the multicast datastream to network elements coupled to those network router elements (e.g., network elements 131 and 132 or network router element 140). In this manner, a multicast datastream from network element 111 can be transmitted through a network to multiple receiving network elements. The path of such a transmission can be thought of as a tree, wherein network element 111 is the root of the tree and network elements 121, 131, 132, and 141 can be thought of as the tips of branches.
FIG. 1B is a simplified block diagram of a network in which multiple sources are transmitting to a multicast group. As in FIG. 1A, network element 111 is a source for a multicast datastream directed to a multicast group including network elements 112, 121, 131, 132, and 141. That multicast datastream is illustrated by path 180 (a solid line). Network element 132 is also transmitting a multicast datastream to the multicast group, and that datastream is illustrated by path 190 (a dashed line). In a multiple source multicast group, any subscriber network element can be a source. In order to provide this two-way routing of multicast data packets, a bi-directional version of protocol independent multicast (PIM bidir) is used to configure the network router elements in the multicast tree. In such bi-directional multicast, datastream packets are routed only along the shared bi-directional tree, which is rooted at a rendezvous point for the multicast group, rather than at a particular datastream source. Logically, a rendezvous point is an address (e.g., address of a network router element) that is “upstream” from all other network elements. Passing all bi-directional multicast traffic through such a rendezvous point, establishes a loop-free tree topology with a root at the rendezvous point. In FIG. 1B, the rendezvous point is illustrated as network router element 110.
FIGS. 1A and 1B illustrate transmission of multicast datastreams in a network in which the network router elements 110, 120, 130 and 140 are directly coupled with one another. But, as stated above, as a business and its network grow, a business' network elements can become geographically diverse, and therefore the path over which the datastream must flow can include an intervening third-party provider transport network.
FIG. 2 is a simplified block diagram illustrating a network configuration in which geographically diverse subnets of a business' network are coupled through a provider transport network 255. The business' network includes network router elements 210, 220, 230, and 240, wherein network router element 210 is coupled to network elements 211 and 212, network router element 220 is coupled to network element 221, network router element 230 is coupled to network elements 231 and 232, and network router element 240 is coupled to network element 241. In order to connect to provider transport network 255, a network router element on the edge of the business' network (a customer edge router) is coupled to a network router element on the edge of the provider network (a provider edge router). In FIG. 2, customer edge router elements 250(1-3) are coupled to provider edge router elements 260(1-3), respectively. Network router element 240 is coupled to provider edge router element 260(4) (that is, network router element 240 is configured as a customer edge router).
It should be noted that the customer edge router and the provider edge router functionality can be provided by a single router. Further, a network router element such as 240 can also serve as an edge router. The provider edge routers provide access to provider transport network 255, which can contain data transmission lines, network router elements, and OSI Level 2 network devices to aid in the transmission of data from one provider edge router to another provider edge router. The provider transport network illustrated in FIG. 2 contains, as an example, network router elements 270(1-5) and 270(r), which are coupled in a manner to permit transmission of packets through the transport network. Such network router elements internal to a transport network are called “core router elements” or “core routers.” A provider transport network is not limited to such a configuration, and can include any number of network router elements, transmission lines, and other L2 and L3 network devices.
In order to facilitate transmission of data through the provider transport network, the transport network can utilize different protocols from those used in coupled customer networks. Such transport network protocols can permit faster data transmission and routing through the network. Any needed translation between customer and provider transport network protocols can be performed by the edge routers.
A provider transport network can have a large number of provider edge routers, each of which can in turn be coupled to a plurality of customer networks. In order to maintain privacy between the various customer networks, network traffic from each of the customer networks can be transmitted in a virtual private network (VPN). Each customer can be allocated one or more VPNs depending on the customer's needs.
FIG. 3 is a simplified block diagram illustrating a provider transport network providing network support for a number of VPNs. Provider transport network 310 comprises, in part, provider edge routers 320(1)-320(M). As illustrated, each of the provider edge routers is also coupled, directly or indirectly, to VPNs 330(1)-330(N). While FIG. 3 shows that each provider edge router is coupled to each VPN, it should be understood that each provider edge router need not be coupled to each and every VPN supported by the provider transport network.
A VPN can be configured to support multicast traffic sent from sources to receivers within that VPN. Each provider edge router that supports a multicast VPN (mVPN) customer is part of the multicast domain for that customer. As shown in FIG. 3, multiple customers can be coupled to a particular provider edge router, which means that a provider edge router can be a member of many multicast domains—one for each mVPN customer who is connected to that provider edge router.
As discussed above, PIM is used by routers in a multicast network to provide information about membership to a multicast group or source and group tuple. A network element can express its interest in receiving traffic destined for a multicast group by transmitting an IGMP or equivalent message to a network router element. Upon receiving the network element's expression of interest, the network router can then send a PIM join message toward a root node for that multicast group (e.g., a rendezvous point or a specified source for that multicast group). Join messages are typically known as (*,G) joins because the join message results in joining group G for all sources to that group or (S,G) joins because the join message results in joining group G for a specified source for that group. The (*,G) or (S,G) join message travels hop-by-hop toward the root node and a multicast tree forwarding state for group G is instantiated in each router through which the (*,G) or (S,G) join passes. Eventually, the (*,G) or (S,G) join reaches the root node, or reaches a router that already has a (*,G) or (S,G) forwarding state for group G or source S and group G. When several network elements join a group, their join messages converge on the root node, and form a distribution tree for group G that is rooted at the root node. Join messages are resent periodically so long as a receiver remains in the group. If all receiving network elements coupled to a particular network router element leave a group, then the network router element will send a PIM (*,G) or (S,G) prune message toward the root node.
PIM also supports other message types necessary to the proper functioning of a multicast network. PIM Hello messages are sent periodically on each PIM-enabled interface. Hello messages allow a router to learn about neighboring PIM routers on each interface. A router records Hello information received from each PIM neighbor. In the PIM protocol, Hello messages must be sent on all active interfaces, including physical point-to-point links, and are multicast to a group address that includes all PIM routers within a broadcast domain. Further, Hello messages must be sent periodically in order to refresh PIM-related tables in each PIM router (for example, a typical default Hello timer is set to 30 seconds). Neighbor routers will not accept join/prune messages or other PIM messages from a router unless the receiving routers have first received a Hello message from the transmitting router. Thus, if a router needs to transmit a join/prune or other PIM message on an interface on which that router has not sent a Hello message, then that router must send a Hello message on that interface followed by the join/prune or other PIM message.
In the provider transport network illustrated in FIG. 3, one or more of VPNs 330 can be configured as a multicast VPN. In a multicast VPN, a provider edge router can be called upon to transmit PIM messages across the transport network to neighboring provider edge routers coupled to that VPN. The receiving provider edge routers will then process the PIM messages, transmitting the messages upstream toward a root node of a multicast group as appropriate. PIM Hello and join/prune messages are broadcast to all neighboring PIM routers.
A separate join/prune message is generated for each implicated neighboring router. Join and prune requests are collected for each router over a period of time (typically 60 seconds) and then a PIM join/prune message is compiled for each neighboring router and broadcast through the mVPN. Thus, the number of join/prune messages that can be generated during a period can be equal to the number of provider edge routers (e.g., M) that are members of a mVPN. Further, a provider edge router will generate join/prune messages for each mVPN coupled to the provider edge router (e.g., N).
In a large scale network, where many mVPNs are supported and many provider edge routers are provided, a significant number of join/prune messages can be periodically generated by each provider edge router. Further, since PIM Hello messages are also periodically transmitted to all neighboring PIM routers, a significant number of Hello messages can also be generated. This PIM join/prune and Hello traffic consumes network bandwidth within the provider transport network and creates processing load on the transmitting provider edge routers to generate the various PIM messages. An additional processing load is experienced by the receiving provider edge routers upon receiving the PIM messages, since each router will receive each broadcast PIM message (other than those generated by that router itself).
It is desirable to reduce the quantity of PIM traffic handled by provider edge routers, thereby decreasing the amount of bandwidth consumed by PIM messages and the transmit and receive load on the provider edge routers.